Search Results

Documents authored by Yannakakis, Mihalis

Document
DOI: 10.4230/LIPIcs.CCC.2023.21
Reducing Tarski to Unique Tarski (In the Black-Box Model)

Authors: Xi Chen, Yuhao Li, and Mihalis Yannakakis

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
We study the problem of finding a Tarski fixed point over the k-dimensional grid [n]^k. We give a black-box reduction from the Tarski problem to the same problem with an additional promise that the input function has a unique fixed point. It implies that the Tarski problem and the unique Tarski problem have exactly the same query complexity. Our reduction is based on a novel notion of partial-information functions which we use to fool algorithms for the unique Tarski problem as if they were working on a monotone function with a unique fixed point.
Cite as

Xi Chen, Yuhao Li, and Mihalis Yannakakis. Reducing Tarski to Unique Tarski (In the Black-Box Model). In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 21:1-21:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.CCC.2023.21,
  author =	{Chen, Xi and Li, Yuhao and Yannakakis, Mihalis},
  title =	{{Reducing Tarski to Unique Tarski (In the Black-Box Model)}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{21:1--21:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.21},
  URN =		{urn:nbn:de:0030-drops-182919},
  doi =		{10.4230/LIPIcs.CCC.2023.21},
  annote =	{Keywords: Tarski fixed point, Query complexity, TFNP}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.88
Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP

Authors: Amol Pasarkar, Christos Papadimitriou, and Mihalis Yannakakis

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
We study the complexity of computational problems arising from existence theorems in extremal combinatorics. For some of these problems, a solution is guaranteed to exist based on an iterated application of the Pigeonhole Principle. This results in the definition of a new complexity class within TFNP, which we call PLC (for "polynomial long choice"). PLC includes all of PPP, as well as numerous previously unclassified total problems, including search problems related to Ramsey’s theorem, the Sunflower theorem, the Erdős-Ko-Rado lemma, and König’s lemma. Whether the first two of these four problems are PLC-complete is an important open question which we pursue; in contrast, we show that the latter two are PPP-complete. Finally, we reframe PPP as an optimization problem, and define a hierarchy of such problems related to Turàn’s theorem.
Cite as

Amol Pasarkar, Christos Papadimitriou, and Mihalis Yannakakis. Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 88:1-88:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{pasarkar_et_al:LIPIcs.ITCS.2023.88,
  author =	{Pasarkar, Amol and Papadimitriou, Christos and Yannakakis, Mihalis},
  title =	{{Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{88:1--88:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.88},
  URN =		{urn:nbn:de:0030-drops-175913},
  doi =		{10.4230/LIPIcs.ITCS.2023.88},
  annote =	{Keywords: Total Complexity, Extremal Combinatorics, Pigeonhole Principle}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.59
Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets

Authors: Vijay V. Vazirani and Mihalis Yannakakis

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
In 1979, Hylland and Zeckhauser [Hylland and Zeckhauser, 1979] gave a simple and general scheme for implementing a one-sided matching market using the power of a pricing mechanism. Their method has nice properties - it is incentive compatible in the large and produces an allocation that is Pareto optimal - and hence it provides an attractive, off-the-shelf method for running an application involving such a market. With matching markets becoming ever more prevalent and impactful, it is imperative to finally settle the computational complexity of this scheme. We present the following partial resolution: 1) A combinatorial, strongly polynomial time algorithm for the dichotomous case, i.e., 0/1 utilities, and more generally, when each agent’s utilities come from a bi-valued set. 2) An example that has only irrational equilibria, hence proving that this problem is not in PPAD. 3) A proof of membership of the problem in the class FIXP. 4) A proof of membership of the problem of computing an approximate HZ equilibrium in the class PPAD. We leave open the (difficult) questions of determining if computing an exact HZ equilibrium is FIXP-hard and an approximate HZ equilibrium is PPAD-hard.
Cite as

Vijay V. Vazirani and Mihalis Yannakakis. Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 59:1-59:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{vazirani_et_al:LIPIcs.ITCS.2021.59,
  author =	{Vazirani, Vijay V. and Yannakakis, Mihalis},
  title =	{{Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{59:1--59:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.59},
  URN =		{urn:nbn:de:0030-drops-135987},
  doi =		{10.4230/LIPIcs.ITCS.2021.59},
  annote =	{Keywords: Hyland-Zeckhauser scheme, one-sided matching markets, mechanism design, dichotomous utilities, PPAD, FIXP}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.18
Tarski’s Theorem, Supermodular Games, and the Complexity of Equilibria

Authors: Kousha Etessami, Christos Papadimitriou, Aviad Rubinstein, and Mihalis Yannakakis

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
The use of monotonicity and Tarski’s theorem in existence proofs of equilibria is very widespread in economics, while Tarski’s theorem is also often used for similar purposes in the context of verification. However, there has been relatively little in the way of analysis of the complexity of finding the fixed points and equilibria guaranteed by this result. We study a computational formalism based on monotone functions on the d-dimensional grid with sides of length N, and their fixed points, as well as the closely connected subject of supermodular games and their equilibria. It is known that finding some (any) fixed point of a monotone function can be done in time log^d N, and we show it requires at least log^2 N function evaluations already on the 2-dimensional grid, even for randomized algorithms. We show that the general Tarski problem of finding some fixed point, when the monotone function is given succinctly (by a boolean circuit), is in the class PLS of problems solvable by local search and, rather surprisingly, also in the class PPAD. Finding the greatest or least fixed point guaranteed by Tarski’s theorem, however, requires d ⋅ N steps, and is NP-hard in the white box model. For supermodular games, we show that finding an equilibrium in such games is essentially computationally equivalent to the Tarski problem, and finding the maximum or minimum equilibrium is similarly harder. Interestingly, two-player supermodular games where the strategy space of one player is one-dimensional can be solved in O(log N) steps. We also show that computing (approximating) the value of Condon’s (Shapley’s) stochastic games reduces to the Tarski problem. An important open problem highlighted by this work is proving a Ω(log^d N) lower bound for small fixed dimension d ≥ 3.
Cite as

Kousha Etessami, Christos Papadimitriou, Aviad Rubinstein, and Mihalis Yannakakis. Tarski’s Theorem, Supermodular Games, and the Complexity of Equilibria. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{etessami_et_al:LIPIcs.ITCS.2020.18,
  author =	{Etessami, Kousha and Papadimitriou, Christos and Rubinstein, Aviad and Yannakakis, Mihalis},
  title =	{{Tarski’s Theorem, Supermodular Games, and the Complexity of Equilibria}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{18:1--18:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.18},
  URN =		{urn:nbn:de:0030-drops-117037},
  doi =		{10.4230/LIPIcs.ITCS.2020.18},
  annote =	{Keywords: Tarski’s theorem, supermodular games, monotone functions, lattices, fixed points, Nash equilibria, computational complexity, PLS, PPAD, stochastic games, oracle model, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.21
The Complexity of Finding S-Factors in Regular Graphs

Authors: Sanjana Kolisetty, Linh Le, Ilya Volkovich, and Mihalis Yannakakis

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract
A graph G has an S-factor if there exists a spanning subgraph F of G such that for all v in V: deg_F(v) in S. The simplest example of such factor is a 1-factor, which corresponds to a perfect matching in a graph. In this paper we study the computational complexity of finding S-factors in regular graphs. Our techniques combine some classical as well as recent tools from graph theory.
Cite as

Sanjana Kolisetty, Linh Le, Ilya Volkovich, and Mihalis Yannakakis. The Complexity of Finding S-Factors in Regular Graphs. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 21:1-21:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kolisetty_et_al:LIPIcs.FSTTCS.2019.21,
  author =	{Kolisetty, Sanjana and Le, Linh and Volkovich, Ilya and Yannakakis, Mihalis},
  title =	{{The Complexity of Finding S-Factors in Regular Graphs}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{21:1--21:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.21},
  URN =		{urn:nbn:de:0030-drops-115834},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.21},
  annote =	{Keywords: constraint satisfaction problem, Dichotomy theorem, Graph Factors, Regular Graphs}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2019.5
Fixed Point Computation Problems and Facets of Complexity (Invited Talk)

Authors: Mihalis Yannakakis

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Many problems from a wide variety of areas can be formulated mathematically as the problem of computing a fixed point of a suitable given multivariate function. Examples include a variety of problems from game theory, economics, optimization, stochastic analysis, verification, and others. In some problems there is a unique fixed point (for example if the function is a contraction); in others there may be multiple fixed points and any one of them is an acceptable solution; while in other cases the desired object is a specific fixed point (for example the least fixed point or greatest fixed point of a monotone function). In this talk we will discuss several types of fixed point computation problems, their complexity, and some of the common themes that have emerged: classes of problems for which there are efficient algorithms, and other classes for which there seem to be serious obstacles.
Cite as

Mihalis Yannakakis. Fixed Point Computation Problems and Facets of Complexity (Invited Talk). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, p. 5:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{yannakakis:LIPIcs.ICALP.2019.5,
  author =	{Yannakakis, Mihalis},
  title =	{{Fixed Point Computation Problems and Facets of Complexity}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{5:1--5:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.5},
  URN =		{urn:nbn:de:0030-drops-105812},
  doi =		{10.4230/LIPIcs.ICALP.2019.5},
  annote =	{Keywords: Fixed Point, Polynomial Time Algorithm, Computational Complexity}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2019.115
Reachability for Branching Concurrent Stochastic Games (Track B: Automata, Logic, Semantics, and Theory of Programming)

Authors: Kousha Etessami, Emanuel Martinov, Alistair Stewart, and Mihalis Yannakakis

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We give polynomial time algorithms for deciding almost-sure and limit-sure reachability in Branching Concurrent Stochastic Games (BCSGs). These are a class of infinite-state imperfect-information stochastic games that generalize both finite-state concurrent stochastic reachability games ([L. de Alfaro et al., 2007]) and branching simple stochastic reachability games ([K. Etessami et al., 2018]).
Cite as

Kousha Etessami, Emanuel Martinov, Alistair Stewart, and Mihalis Yannakakis. Reachability for Branching Concurrent Stochastic Games (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 115:1-115:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{etessami_et_al:LIPIcs.ICALP.2019.115,
  author =	{Etessami, Kousha and Martinov, Emanuel and Stewart, Alistair and Yannakakis, Mihalis},
  title =	{{Reachability for Branching Concurrent Stochastic Games}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{115:1--115:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.115},
  URN =		{urn:nbn:de:0030-drops-106917},
  doi =		{10.4230/LIPIcs.ICALP.2019.115},
  annote =	{Keywords: stochastic games, multi-type branching processes, concurrent games, minimax-polynomial equations, reachability, almost-sure, limit-sure}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.615
Temporal Synthesis for Bounded Systems and Environments

Authors: Orna Kupferman, Yoad Lustig, Moshe Y. Vardi, and Mihalis Yannakakis

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
Temporal synthesis is the automated construction of a system from its temporal specification. It is by now realized that requiring the synthesized system to satisfy the specifications against all possible environments may be too demanding, and, dually, allowing all systems may be not demanding enough. In this work we study bounded temporal synthesis, in which bounds on the sizes of the state space of the system and the environment are additional parameters to the synthesis problem. This study is motivated by the fact that such bounds may indeed change the answer to the synthesis problem, as well as the theoretical and computational aspects of the synthesis problem. In particular, a finer analysis of synthesis, which takes system and environment sizes into account, yields deeper insight into the quantificational structure of the synthesis problem and the relationship between strong synthesis -- there exists a system such that for all environments, the specification holds, and weak synthesis -- for all environments there exists a system such that the specification holds. We first show that unlike the unbounded setting, where determinacy of regular games implies that strong and weak synthesis coincide, these notions do not coincide in the bounded setting. We then turn to study the complexity of deciding strong and weak synthesis. We show that bounding the size of the system or both the system and the environment, turns the synthesis problem into a search problem, and one cannot expect to do better than brute-force search. In particular, the synthesis problem for bounded systems and environment is Sigma^P_2-complete (in terms of the bounds, for a specification given by a deterministic automaton). We also show that while bounding the environment may lead to the synthesis of specifications that are otherwise unrealizable, such relaxation of the problem comes at a high price from a complexity-theoretic point of view.
Cite as

Orna Kupferman, Yoad Lustig, Moshe Y. Vardi, and Mihalis Yannakakis. Temporal Synthesis for Bounded Systems and Environments. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 615-626, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{kupferman_et_al:LIPIcs.STACS.2011.615,
  author =	{Kupferman, Orna and Lustig, Yoad and Vardi, Moshe Y. and Yannakakis, Mihalis},
  title =	{{Temporal Synthesis for Bounded Systems and Environments}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{615--626},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.615},
  URN =		{urn:nbn:de:0030-drops-30481},
  doi =		{10.4230/LIPIcs.STACS.2011.615},
  annote =	{Keywords: temporal synthesis}
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1311
Equilibria, Fixed Points, and Complexity Classes

Authors: Mihalis Yannakakis

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
Many models from a variety of areas involve the computation of an equilibrium or fixed point of some kind. Examples include Nash equilibria in games; market equilibria; computing optimal strategies and the values of competitive games (stochastic and other games); stable configurations of neural networks; analysing basic stochastic models for evolution like branching processes and for language like stochastic context-free grammars; and models that incorporate the basic primitives of probability and recursion like recursive Markov chains. It is not known whether these problems can be solved in polynomial time. There are certain common computational principles underlying different types of equilibria, which are captured by the complexity classes PLS, PPAD, and FIXP. Representative complete problems for these classes are respectively, pure Nash equilibria in games where they are guaranteed to exist, (mixed) Nash equilibria in 2-player normal form games, and (mixed) Nash equilibria in normal form games with 3 (or more) players. This paper reviews the underlying computational principles and the corresponding classes.
Cite as

Mihalis Yannakakis. Equilibria, Fixed Points, and Complexity Classes. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 19-38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{yannakakis:LIPIcs.STACS.2008.1311,
  author =	{Yannakakis, Mihalis},
  title =	{{Equilibria, Fixed Points, and Complexity Classes}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{19--38},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1311},
  URN =		{urn:nbn:de:0030-drops-13110},
  doi =		{10.4230/LIPIcs.STACS.2008.1311},
  annote =	{Keywords: Equilibria, Fixed points, Computational Complexity, Game Theory}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact